/*
 * CGenAlg.java
 * 
 * Created on Mar 24, 2008, 11:08:45 AM
 * 
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package com.leadiv.ai.ga;

import java.io.IOException;
import java.util.Collections;
import java.util.Iterator;
import java.util.Vector;
import com.leadiv.ai.minesweeper.util.Params;
import com.leadiv.ai.minesweeper.util.Utils;
import org.xml.sax.SAXException;

/**
 *
 * @author leadiv
 */
public class CGenAlg {
    
    //this holds the entire population of chromosomes
    private Vector<SGenome> m_vecPop = new Vector<SGenome>();
    
    //size of population
    private int m_iPopSize = 0;
	
    //amount of weights per chromo
    private int m_iChromoLength = 0;

    //total fitness of population
    private double m_dTotalFitness = 0.0;

    //best fitness this population
    private double m_dBestFitness = 0.0;

    //average fitness
    private double m_dAverageFitness = 0.0;

    //worst
    private double m_dWorstFitness = 0.0;

    //keeps track of the best genome
    private int m_iFittestGenome = 0;

    //probability that a chromosones bits will mutate.
    //Try figures around 0.05 to 0.3 ish
    private double m_dMutationRate = 0.0;

    //probability of chromosones crossing over bits
    //0.7 is pretty good
    private double m_dCrossoverRate = 0.0;

    //generation counter
    private int m_cGeneration = 0;
    
    //-----------------------------------constructor-------------------------
    //
    //	sets up the population with random floats
    //
    //-----------------------------------------------------------------------
    public CGenAlg(int popsize, double MutRat, double CrossRat, int numweights)
    {
        m_iPopSize = popsize;
        m_dMutationRate = MutRat;
        m_dCrossoverRate = CrossRat;
        m_iChromoLength = numweights;
        m_dTotalFitness = 0;
        m_cGeneration = 0;
        m_iFittestGenome = 0;
        m_dBestFitness = 0;
        m_dWorstFitness = 99999999;
        m_dAverageFitness = 0;
        
	//initialise population with chromosomes consisting of random
	//weights and all fitnesses set to zero
	for (int i=0; i<m_iPopSize; ++i)
	{
            m_vecPop.add(new SGenome());

            for (int j=0; j<m_iChromoLength; ++j)
            {
                m_vecPop.get(i).vecWeights.add(Utils.RandomClamped());
            }
	}
    }
    
    //-------------------------------------Crossover()-----------------------
    //	
    //  given parents and storage for the offspring this method performs
    //	crossover according to the GAs crossover rate
    //-----------------------------------------------------------------------
    // mun and dad should not have their data modified!!!!
    // SINCE THEY ARE ALL OBJECTS THEY ARE ALL PASSED BY REFERENCED.
    private void Crossover(Vector<Double> mum, Vector<Double> dad, Vector<Double> baby1, Vector<Double> baby2)
    {
        int i = 0; // counter
        
        //just return parents as offspring dependent on the rate
        //or if parents are the same
        if ( (Utils.RandFloat() > m_dCrossoverRate) || (mum == dad)) 
        {
            baby1 = mum;
            baby2 = dad;

            return;
        }

        //determine a crossover point
        int cp = Utils.RandInt(0, m_iChromoLength - 1);

        //create the offspring
        for (i=0; i<cp; ++i)
        {
            baby1.add(mum.get(i));
            baby2.add(dad.get(i));
        }

        for (i=cp; i<mum.size(); ++i)
        {
            baby1.add(dad.get(i));
            baby2.add(mum.get(i));
        }


        return;
    }

    //---------------------------------Mutate--------------------------------
    //
    //	mutates a chromosome by perturbing its weights by an amount not 
    //	greater than CParams::dMaxPerturbation
    //-----------------------------------------------------------------------
    // SINCE chromo IS AN OBJECTS IT IS PASSED BY REFERENCE.
    private void Mutate(Vector<Double> chromo) throws SAXException, IOException
    {
	//traverse the chromosome and mutate each weight dependent
	//on the mutation rate
        Params p = new Params();
        
	for (int i=0; i<chromo.size(); ++i)
	{
		//do we perturb this weight?
		if (Utils.RandFloat() < m_dMutationRate)
		{
			//add or subtract a small value to the weight
			chromo.set(i, chromo.get(i) + (Utils.RandomClamped() * p.dMaxPerturbation));
		}
	}
    }

    //----------------------------------GetChromoRoulette()------------------
    //
    //	returns a chromo based on roulette wheel sampling
    //
    //-----------------------------------------------------------------------
    private SGenome GetChromoRoulette()
    {
        //generate a random number between 0 & total fitness count
        double Slice = (double)(Utils.RandFloat() * m_dTotalFitness);

        //this will be set to the chosen chromosome
        SGenome TheChosenOne = new SGenome();

        //go through the chromosones adding up the fitness so far
        double FitnessSoFar = 0.0;

        for (int i=0; i<m_iPopSize; ++i)
        {
            FitnessSoFar += m_vecPop.get(i).dFitness;

            //if the fitness so far > random number return the chromo at 
            //this point
            if (FitnessSoFar >= Slice)
            {
                TheChosenOne = m_vecPop.get(i);
                break;
            }

        }

        return TheChosenOne;
    }

    
    //-------------------------GrabNBest----------------------------------
    //
    //	This works like an advanced form of elitism by inserting NumCopies
    //  copies of the NBest most fittest genomes into a population vector
    //--------------------------------------------------------------------
    //use to introduce elitism
    // NumCopies SHOULD NOT BE MODIFIED.
    // vecPop IS AN OBJECT AND SO IS PASSED BY REFERENCE.
    private void GrabNBest(int NBest, int NumCopies, Vector<SGenome> vecPop)
    {
        //add the required amount of copies of the n most fittest 
        //to the supplied vector
        while(NBest-- != 0)
        {
                for (int i=0; i<NumCopies; ++i)
                {
                        vecPop.add(m_vecPop.get((m_iPopSize - 1) - NBest));
          }
        }
    }

    //-----------------------CalculateBestWorstAvTot-----------------------	
    //
    //	calculates the fittest and weakest genome and the average/total 
    //	fitness scores
    //---------------------------------------------------------------------
    private void CalculateBestWorstAvTot()
    {
        m_dTotalFitness = 0;

        double HighestSoFar = 0;
        double LowestSoFar  = 9999999;

        for (int i=0; i<m_iPopSize; ++i)
        {
            //update fittest if necessary
            if (m_vecPop.get(i).dFitness > HighestSoFar)
            {
                HighestSoFar = m_vecPop.get(i).dFitness;
                m_iFittestGenome = i;
                m_dBestFitness	 = HighestSoFar;
            }

            //update worst if necessary
            if (m_vecPop.get(i).dFitness < LowestSoFar)
            {
                LowestSoFar = m_vecPop.get(i).dFitness;

                m_dWorstFitness = LowestSoFar;
            }

            m_dTotalFitness += m_vecPop.get(i).dFitness;


        }//next chromo

        m_dAverageFitness = m_dTotalFitness / m_iPopSize;
    }

    private void Reset()
    {
        m_dTotalFitness = 0;
        m_dBestFitness = 0;
        m_dWorstFitness = 9999999;
        m_dAverageFitness = 0;
    }
    
    //-----------------------------------Epoch()-----------------------------
    //
    //	takes a population of chromosones and runs the algorithm through one
    //	 cycle.
    //	Returns a new population of chromosones.
    //
    //-----------------------------------------------------------------------
    //this runs the GA for one generation.
    public Vector<SGenome> Epoch(Vector<SGenome> old_pop) throws SAXException, IOException
    {
        Params p = new Params();
        
	//assign the given population to the classes population
        m_vecPop.clear();
        Iterator<SGenome> vals = old_pop.iterator();
        
        while(vals.hasNext())
        {
            m_vecPop.add(vals.next());
        }

        //reset the appropriate variables
        Reset();

        //sort the population (for scaling and elitism)
        Collections.sort(m_vecPop);

        //calculate best, worst, average and total fitness
        CalculateBestWorstAvTot();

        //create a temporary vector to store new chromosones
        Vector<SGenome> vecNewPop = new Vector<SGenome>();

	//Now to add a little elitism we shall add in some copies of the
	//fittest genomes. Make sure we add an EVEN number or the roulette
        //wheel sampling will crash
	if ((p.iNumCopiesElite * p.iNumElite % 2) == 0)
	{
            GrabNBest((int)p.iNumElite, (int)p.iNumCopiesElite, vecNewPop);
	}
	

	//now we enter the GA loop
	
	//repeat until a new population is generated
	while (vecNewPop.size() < m_iPopSize)
	{
            //grab two chromosones
            SGenome mum = GetChromoRoulette();
            SGenome dad = GetChromoRoulette();

            //create some offspring via crossover
            Vector<Double> baby1 = new Vector<Double>();
            Vector<Double> baby2 = new Vector<Double>();

            Crossover(mum.vecWeights, dad.vecWeights, baby1, baby2);

            //now we mutate
            Mutate(baby1);
            Mutate(baby2);

            //now copy into vecNewPop population
            vecNewPop.add(new SGenome(baby1, 0));
            vecNewPop.add(new SGenome(baby2, 0));
	}

	//finished so assign new pop back into m_vecPop
        m_vecPop.clear();
        vals = vecNewPop.iterator();
        
        while(vals.hasNext())
        {
            m_vecPop.add(vals.next());
        }
        
	return m_vecPop;
    }

    //-------------------accessor methods
    public Vector<SGenome> GetChromos()
    {
        return m_vecPop;
    }
    
    public double AverageFitness()
    {
        return m_dTotalFitness / m_iPopSize;
    }
    
    public double BestFitness() 
    {
        return m_dBestFitness;
    }
}
	